Luồng cực đại là gì? Các công bố khoa học về Luồng cực đại
Luồng cực đại (Maximum Flow) là một khái niệm trong lý thuyết đồ thị. Nó liên quan đến việc tìm cách lưu lượng truyền qua một mạng lưới từ một đỉnh nguồn (sourc...
Luồng cực đại (Maximum Flow) là một khái niệm trong lý thuyết đồ thị. Nó liên quan đến việc tìm cách lưu lượng truyền qua một mạng lưới từ một đỉnh nguồn (source) đến một đỉnh đích (sink) sao cho lưu lượng này là lớn nhất có thể.
Trong một mạng lưới, các đỉnh biểu thị vị trí và các cạnh biểu thị đường truyền thông giữa các vị trí đó. Mỗi cạnh có một số liệu gọi là khả năng chứa lưu lượng (capacity) - tức là lưu lượng tối đa có thể truyền qua cạnh đó.
Luồng cực đại tìm cách phân phối lưu lượng từ đỉnh nguồn đến đỉnh đích sao cho:
1. Lưu lượng trên mỗi cạnh không vượt quá khả năng chứa của cạnh đó.
2. Tổng lưu lượng đi qua mạng lưới là lớn nhất.
Để tìm luồng cực đại, các thuật toán như thuật toán Ford-Fulkerson hoặc thuật toán Edmonds-Karp được sử dụng. Các thuật toán này đều dựa trên khái niệm "đường cắt" (cut) trong đồ thị và sử dụng việc tăng cường đường đi (augmenting path) để tăng giá trị lưu lượng truyền qua mạng lưới.
Để hiểu chi tiết hơn về luồng cực đại, ta cần biết thêm một số khái niệm và thuật ngữ liên quan.
1. Đồ thị mạng (Network graph): Đồ thị mạng được sử dụng để biểu diễn một hệ thống hay mạng gồm các vị trí (đỉnh) và các đường truyền thông (cạnh) giữa chúng. Đồ thị mạng bao gồm một đỉnh nguồn (s) và một đỉnh đích (t), cùng với các đỉnh và cạnh khác.
2. Khả năng chứa lưu lượng (Capacity): Mỗi cạnh trong đồ thị mạng có một giá trị thể hiện lưu lượng tối đa mà cạnh đó có thể truyền qua. Đây là một giá trị không âm và có thể khác nhau cho từng cạnh.
3. Luồng (Flow): Một luồng trên đồ thị mạng là một phân phối của lưu lượng từ đỉnh nguồn đến đỉnh đích qua các cạnh. Luồng trên một cạnh phải thỏa mãn các ràng buộc sau:
- Không vượt quá khả năng chứa của cạnh: Lưu lượng trên mỗi cạnh phải nhỏ hơn hoặc bằng khả năng chứa của cạnh đó.
- Cân bằng luồng tại các đỉnh ngoại trừ đỉnh nguồn và đích: Tổng lưu lượng đến một đỉnh (trừ đỉnh nguồn và đích) phải bằng tổng lưu lượng ra khỏi đỉnh đó.
4. Luồng cực đại (Maximum Flow): Luồng cực đại trên một đồ thị mạng là luồng có tổng lưu lượng trên các cạnh là lớn nhất có thể. Điều này có nghĩa là không thể tăng giá trị của luồng bằng cách phân phối lưu lượng khác.
Thuật toán Ford-Fulkerson và Edmonds-Karp là hai phương pháp được sử dụng để tìm luồng cực đại trên đồ thị mạng. Cả hai thuật toán này đều dựa trên việc tìm đường đi từ đỉnh nguồn đến đỉnh đích (đường cắt) có thể cung cấp một lượng lưu lượng khả dụng tiếp theo để tăng giá trị của luồng. Thuật toán tiếp tục tìm kiếm đường đi này và tăng giá trị lưu lượng cho đến khi không còn đường đi nữa. Khi đó, luồng đã đạt đến cực đại.
Luồng cực đại có ứng dụng trong nhiều lĩnh vực như mạng máy tính, điều độ giao thông, lập lịch công việc, v.v.
Danh sách công bố khoa học về chủ đề "luồng cực đại":
Để hiểu nguồn gốc của sự xuất hiện lớp sụn trong hình ảnh MRI (hiệu ứng góc kỳ diệu), các thí nghiệm MRI vi mô (μMRI) được thực hiện với độ phân giải pixel 14 μm trên sụn khớp bình thường của chó ở các khớp vai. Các hình ảnh hai chiều về thời gian nghỉ spin-spin (T2) của nút sụn-xương tại hai góc (0° và 55°) được tính toán một cách định lượng. Một sự dị hướng T2 rõ rệt đã được quan sát như một chức năng của độ sâu của mô sụn. Khu vực bề mặt và các vùng sâu bộc lộ sự phụ thuộc định hướng mạnh mẽ của T2, trong khi khu vực trên giữa cho thấy ít sự phụ thuộc định hướng của T2. Ba vùng μMRI này tương ứng gần như với ba khu vực mô học trong mô sụn. Kết quả từ các đo đạc T2 đại diện thống nhất với những kết quả μMRI này. Các nghiên cứu của chúng tôi cho thấy sự xuất hiện lớp sụn trong MRI được gây ra bởi sự dị hướng T2 của mô. Chúng tôi cũng đề xuất rằng nguồn gốc phân tử của sự dị hướng T2 là tương tác lưỡng cực hạt nhân. Cấu trúc của mô sụn chỉ ra rằng lưới collagen xác định sự dị hướng T2 này. Các kết quả cho thấy rằng sự dị hướng T2 cung cấp một chỉ số gián tiếp nhưng nhạy cảm cho định hướng của các cấu trúc đại phân tử trong mô sụn. Những ứng dụng lâm sàng của sự dị hướng này được thảo luận.
Một biến thể của phương pháp hồi quy bình phương tối thiểu được phát triển và đánh giá nhằm ước lượng nhiệt độ tối đa và tối thiểu hàng ngày bị thiếu, đặc biệt là đối với các giá trị cực trị nhiệt độ. Phương pháp này tập trung vào việc thu được những ước lượng chính xác về số ngày vượt quá (ví dụ: số ngày có nhiệt độ tối đa hàng ngày lớn hơn hoặc bằng centiles 90) hàng năm, cũng như số lần sự kiện liên tiếp vượt quá, trong khi giới hạn sai số ước lượng liên quan đến từng giá trị đơn lẻ.
Hiệu suất của phương pháp này được so sánh với hai phương pháp hiện có đã được phát triển cho toàn bộ phân phối nhiệt độ. Trong các phương pháp hiện có này, các ước lượng nhiệt độ được dựa trên dữ liệu từ các trạm lân cận bằng cách sử dụng hoặc phương pháp hồi quy hoặc phương pháp dựa trên sự thay đổi nhiệt độ.
Việc đánh giá phương pháp của chúng tôi bằng cách sử dụng nhiệt độ tối thiểu lạnh và tối đa ấm cho thấy phần trăm trung vị của số lần vượt quá được xác định chính xác là 97% và phần trăm trung vị của số lần vượt quá liên tiếp được xác định chính xác là 98%. Các phương pháp hiện có khác có xu hướng đánh giá thấp cả số lần vượt quá đơn lẻ và liên tiếp. Sử dụng các quy trình này, các số lần vượt quá ước lượng thường ít hơn 80% so với những gì đã thực sự xảy ra.
Mặc dù phương pháp của chúng tôi được tinh chỉnh để ước lượng số lần vượt quá, độ chính xác ước lượng của các giá trị nhiệt độ tối đa hoặc tối thiểu hàng ngày riêng lẻ tương tự như các quy trình ước lượng khác. Sai số tuyệt đối trung vị (MAE) sử dụng tất cả các nhiệt độ lớn hơn hoặc bằng centiles 90 (
Tóm tắt. Chúng tôi đã phát triển một hệ thống đồng hóa dữ liệu carbon để ước lượng các dòng carbon bề mặt. Hệ thống này sử dụng bộ lọc Kalman chuyển đổi tổ hợp cục bộ (LETKF) và mô hình vận chuyển khí quyển GEOS-Chem được dẫn động bởi phân tích lại các trường khí tượng của MERRA-1 dựa trên mô hình Hệ thống Quan sát Trái Đất Goddard phiên bản 5 (GEOS-5). Hệ thống đồng hóa này lấy cảm hứng từ phương pháp của Kang và cộng sự (2011, 2012), những người đã ước tính dòng carbon bề mặt trong một thí nghiệm mô phỏng hệ thống quan sát (OSSE) như là các tham số thay đổi trong việc đồng hóa CO2 khí quyển, sử dụng cửa sổ đồng hóa ngắn 6 giờ. Họ đã bao gồm đồng hóa các biến khí tượng tiêu chuẩn, để tổ hợp mang lại một thước đo của độ không chắc chắn trong việc vận chuyển CO2. Sau khi giới thiệu các kỹ thuật mới như 'định vị biến động' và tăng trọng số quan sát gần bề mặt, họ đã đạt được các dòng carbon bề mặt chính xác ở độ phân giải điểm lưới. Chúng tôi đã phát triển một phiên bản mới của bộ lọc Kalman chuyển đổi tổ hợp cục bộ liên quan đến phương pháp 'ra-vào tại chỗ' (RIP) để tăng tốc giai đoạn tăng vòng của đồng hóa dữ liệu bộ lọc Kalman tổ hợp (EnKF) (Kalnay và Yang, 2010; Wang và cộng sự, 2013; Yang và cộng sự, 2012). Giống như RIP, hệ thống đồng hóa mới sử dụng thuật toán 'làm mịn không chi phí' cho LETKF (Kalnay và cộng sự, 2007b), cho phép dịch chuyển nghiệm của bộ lọc Kalman tiến hoặc lùi trong cửa sổ đồng hóa mà không tốn chi phí nào. Trong sơ đồ mới, một 'cửa sổ quan sát' dài (ví dụ, 7 ngày hoặc lâu hơn) được sử dụng để tạo ra tổ hợp LETKF sau 7 ngày. Sau đó, bộ làm mịn RIP được dùng để tạo ra phân tích cuối cùng chính xác trong 1 ngày. Cách tiếp cận mới này có lợi thế là dựa trên cửa sổ đồng hóa ngắn, điều này giúp nó chính xác hơn, và được tiếp xúc với những quan sát tương lai trong 7 ngày, điều này cải thiện phân tích và tăng tốc giai đoạn tăng vòng. Cửa sổ đồng hóa và quan sát sau đó được lùi lên trước 1 ngày, và quy trình này được lặp lại. Điều này giảm đáng kể lỗi phân tích, cho thấy rằng phương pháp đồng hóa mới được phát triển có thể được sử dụng với các mô hình hệ thống Trái Đất khác, đặc biệt là để tận dụng tốt hơn các quan sát kết hợp với các mô hình này.
- 1
- 2
- 3
- 4